int sum[N], ch[N][2], tag[N], fa[N], 
inline void pushup(int p) { sum[p] = sum[ch[p][0]] ^ val[p] ^ sum[ch[p][1]]; } 
inline void reverse(int p) { swap(ch[p][0], ch[p][1]), tag[p] ^= 1; }
inline void pushdown(int p)
{
    if (!tag[p]) return;
    reverse(ch[p][0]), reverse(ch[p][1]), tag[p] = 0;
}
inline void push(int p)
{
    if (!is_root(p)) push(fa[p]);
    pushdown(p);
}
inline int get(int p) { return ch[fa[p]][1] == p; }
inline bool is_root(int p) { return ch[fa[p]][0] != p && ch[fa[p]][1] != p; }
inline void rotate(int p)
{
    int f = fa[p], g = fa[f], k = get(p);
    if (!is_root(f)) ch[g][get(f)] = p;
    ch[f][k] = ch[p][k ^ 1], fa[ch[p][k ^ 1]] = f;
    ch[p][k ^ 1] = f, fa[f] = p, fa[p] = g;
    pushup(f), pushup(p);
}
inline void splay(int p)
{
    push(p); // 注意先把 p 上面的一部分的标记全清掉
    for (int f; f = fa[p], !is_root(p); rotate(p))
        if (!is_root(f)) rotate(get(p) == get(f) ? f : p);
}
inline void access(int p)
{
    for (int child = 0; p; child = p, p = fa[p]) splay(p), ch[p][1] = child, pushup(p);
}
inline void makeroot(int p) { access(p), splay(p), reverse(p); }
inline void split(int u, int v) { makeroot(u), access(v), splay(v); }
inline int findroot(int p)
{
    access(p), splay(p), pushdown(p);
    while (ch[p][0]) p = ch[p][0], pushdown(p);
    return splay(p), p;
}
inline void link(int u, int v) { makeroot(u), fa[u] = v; }
inline void cut(int u, int v)
{
    makeroot(u);
    if (findroot(v) == u && fa[v] == u && !ch[v][0]) fa[v] = ch[u][1] = 0, pushup(u);
}